#include "cllist.h"
/*
 * Author : xgqin@guet.edu.cn
 * Date   : 2013/04/28
 * Description: Create an empty cycle link list with a head node
 * @param : none
 * @return : CLList, NULL point if the creation is failed, else a CLList
 *           is returned
 */
CLList createCLList(void)
{
    CLList list;
    list = (CLList) malloc(sizeof(struct clList));
    if (list == NULL)
    {
        return NULL;
    }
    
    list->head = (PNode) malloc(sizeof(struct CLNode));
    if (list->head == NULL)
    {
        free(list);
        return NULL;
    }
    
    list->head->link = list->head;
    list->rear = list->head;
    list->length = 0;
    
    return list;
}

POSITION locateVertexCLList(CLList list, ELEMTYPE x)
{
    POSITION p;
    
    if (list == NULL)
    {
        return NULL;
    }
    
    p = list->head->link;

    while (p != list->head && p->info != x)
    {
        p = p->link;
    }
   
    if (p == list->head)
    {
        p = NULL;
    }
    
    #ifdef DEBUG
    if (p != NULL)
    {
        printf("ELEMENT %d is found in this cllist, the address is %u\n", x, p);
    }
    else
    {
        printf("ELEMENT %d is not found in this cllist\n", x);
    }
    #endif
    return p;
}

POSITION getPositionByIndexCLList(CLList list, SIZE_T index)
{
    POSITION p;
    SIZE_T i, length;
    
    if (list == NULL)
    {
        return NULL;
    }
    
    length = lengthCLList(list);
    
    if (index > length)
    {
        #ifdef DEBUG
        printf("=============INDEX TO POSITION===========\n");
        printf("Index IS INVALID\n");
        printf("=============INDEX TO POSITION===========\n");
        #endif
        return NULL;
    }
    
    for (i = 0, p = list->head->link; i < index - 1; i++)
    {
        p = p->link;
        if (p == list->head->link)
        {
           p= p->link;
        }
    }
    
    #ifdef DEBUG
    printf("=============INDEX TO POSITION===========\n");
    printf("Index = %d, POSITION = %u\n", index, p);
    printf("=============INDEX TO POSITION===========\n");
    #endif
    return p;
}

int insertPostCLList(CLList list, POSITION p, ELEMTYPE x)
{
    PNode q;

    if (list == NULL || p == NULL)
    {
        return 0;
    }

    q = (PNode) malloc(sizeof(struct CLNode));
    
    if (q != NULL)
    {
        q->info = x;
        q->link = p->link;
        p->link = q;
        list->length++;
        return 1;
    }

    return -1;
}

int insertPreCLList(CLList list, POSITION p, ELEMTYPE x)
{
    PNode q, l;

    if (list == NULL || p == NULL)
    {
        return 0;
    }

    q = (PNode) malloc(sizeof(struct CLNode));
    
    if (q != NULL)
    {
        q->info = x;
        l = list->head;

        while (l->link != p && l->link != list->head)
        {
            l = l->link;
        }
        if (l->link != list->head)
        {
            q->link = l->link;
            l->link = q;
            list->length++;
            return 1;
        }
    }

    return -1;
}

int deleteElemCLList(CLList list, ELEMTYPE x)
{
    PNode p, q;
    #ifdef DEBUG
    SIZE_T i=0;
    #endif

    if (list == NULL)
    {
        return -1;
    }
    
    p = list->head;

    while (p->link->info != x && p->link != list->head)
    {
        p = p->link;
        #ifdef DEBUG
        i++;
        #endif
    }
    
    if (p->link != list->head)
    {
        q = p->link;
        p->link = q->link;
        #ifdef DEBUG
        printf("\n==================NODE WILL BE DELETED============================\n");
        printf("node[%d]->info = %d, address = %u, node[%d]->link = %u \n", i, q->info, q, i, q->link);
        printf("==================NODE WILL BE DELETED============================\n");
        #endif
        free(q);
        return 1;
    }

    #ifdef DEBUG
    printf("\n==================NODE WITH INFO AS %d NOT FOUND======================\n", x);
    printf("==================NO NODE WILL BE DELETED============================\n");
    #endif
    return 0;
}

int deleteVertexCLList(CLList list, POSITION p)
{
    PNode q;
    #ifdef DEBUG
    SIZE_T i=0;
    #endif

    if (list == NULL)
    {
        return -1;
    }
    
    q = list->head;
    
    while (q->link != p && q->link != list->head)
    {
       q = q->link;
        #ifdef DEBUG
        i++;
        #endif
    }
    
    if (q->link != list->head)
    {
        q->link = p->link;
        #ifdef DEBUG
        printf("\n==================NODE WILL BE DELETED============================\n");
        printf("node[%d]->info = %d, address = %u, node[%d]->link = %u \n", i, p->info, p, i, p->link);
        printf("==================NODE WILL BE DELETED============================\n");
        #endif
        free(p);
        list->length = list->length - 1;
        return 1;
    }
    
    return 0;
}

int appendElemCLList(CLList list, ELEMTYPE x)
{
    PNode p;

    if (list == NULL)
    {
        return -1;
    }
    
    p = (PNode) malloc(sizeof(struct CLNode));
    
    if (p != NULL)
    {
        p->info = x;
        p->link = list->rear->link;
        list->rear->link = p;
        
        list->rear = p;
        list->length++;
        return 1;
    }
    
    return 0;
}

void printCLList(CLList list)
{
    POSITION p;
    int i;
    
    if (list == NULL)
    {
        return ;
    }

    p = list->head->link;
    i = 0;
    #ifdef DEBUG
    i = -1;
    p = list->head;
    printf("\n==================HEAD NODE============================\n");
    printf("node[%d]->info = %d, address = %u, node[%d]->link = %u \n", i, p->info, p, i, p->link);
    printf("=====================START=============================\n");
    i++;
    p = list->head->link;
    #endif
    while (p != list->head)
    {
        printf("node[%d]->info = %d, address = %u, node[%d]->link = %u \n", i, p->info, p, i, p->link);
        i++;
        p = p->link;
    }
    #ifdef DEBUG
    printf("======================END=============================\n");
    #endif
}

void destroyCLList(CLList *list)
{
    PNode p, q;

    if (*list == NULL)
    {
        return ;
    }

    p = (*list)->head;

    do {
        q = p;
        p = p->link;
        free(q);
    } while (p != (*list)->head);
/*
    while (p != NULL)
    {
        q = p;
        p = p->link;
        free(q);
    }
*/
    
    free(*list);
    *list = NULL;
}

int lengthCLList(CLList list)
{
    if (list != NULL)
    {
        return list->length;
    }
    return -1;
}
